/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lily
 * Date: 2024-10-30
 * Time: 11:32
 */
public class count_Arrangement {

    boolean[] check;
    int ret;


    public int countArrangement(int n) {
        check = new boolean[n+1];
        dfs(1, n);
        return ret;
    }

    private void dfs(int pos, int n) {
        if (pos == n + 1) {
            ret++;
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (!check[i] && (i % pos == 0 || pos % i == 0)) {
                check[i] = true;
                dfs(pos + 1, n);
                check[i] = false;
            }
        }
    }
}
